Relational Database Management Systems (RDBMS) are well known in the art. An RDBMS is a database management system (DBMS) which uses relational techniques for storing and retrieving information. Relational databases are organized into tables that include rows and columns of data. A database will typically have numerous tables and each table will usually have multiple rows and columns. The tables are typically stored on direct access storage devices (DASD) such as magnetic or optical disk drives for semi-permanent storage.
Records of a database table can be accessed using an index when searching for a particular column value or range of values. An index is an auxiliary data structure that identifies a subset of the records in the table for any given key value. An index key is usually a column or an ordered set of columns of the table. A record-based index maintains record identifiers (RIDs) for each index key value. Hence, they provide a quick method to access the specific subset of records for any given key value. Without an index, finding a record would be more difficult and time-consuming. It would involve scanning an entire table for the value or range of values. Thus, indexes provide an alternate technique to sequential scanning, and can be quite useful if they are defined on keys that are frequently queried. After a table is defined, a user can define one or more indexes by specifying one or more columns of the table as the key for each index. Additionally, several RDBMSs permit a table to be partitioned into one or more subsets of records using partition keys. Record-based indexes can be defined for each partition of the table. Such an index is called a partitioned record index. For any given index key, the partitioned record index only contains RIDs for the records inside the partition that contain the given key value. Record-based indexes can be maintained using several methods. The B-Tree index and Hash index are two popular indexing methods in the current art and are supported by several RDBMSs.
Although record-based indexes and partition-based indexes provide useful ways to access information in a relational database, they have some drawbacks as well. In particular, record-based indexes and partition-based indexes can take up a relatively large amount of storage space, and their processing overhead can be substantial.